/** 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
package com.chen.Leet;

import java.util.Arrays;

public class Soultion {
	public static  int searchInsert(int[] nums, int target) {
		int low = 0, high = nums.length - 1, mid;
		if (nums.length == 0)
			return 0;
		while (low <= high) {
			mid = (low + high) / 2; // 取中间位置
			if (nums[mid] == target)
				return mid;
			else if (nums[mid] > target)
				high = mid - 1;
			else
				low = mid + 1;
		}
		return low;
	}

	public static void main(String[] args) {
		// 输入: nums = [1,3,5,6], target = 5
		// 输出: 2
		int nums[] = { 1,3,5,6 };
		int target = 2;
		System.out.println(searchInsert(nums, target));

	}

}
